/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 38917
 * Date: 2025/5/14
 * Time: 23:06
 */
class BinaryTree {
    public static class TreeNode {
        int value;
        TreeNode left;
        TreeNode right;
        //
        public TreeNode(int value) {
            this.value = value;
        }
    }
    //
    public TreeNode createTree() {
        TreeNode node1 = new TreeNode(3);
        TreeNode node2 = new TreeNode(4);
        TreeNode node3 = new TreeNode(5);
        TreeNode node4 = new TreeNode(1);
        TreeNode node5 = new TreeNode(2);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        return node1;
    }
}
public class Solution {
    private static final BinaryTree.TreeNode root = new BinaryTree().createTree();
    //O(N*2)
    /*public static boolean isBalanced(BinaryTree.TreeNode root){
        if(root == null){
            return true;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return Math.abs(leftHeight - rightHeight) <= 1
                && isBalanced(root.left)
                && isBalanced(root.right);
    }
    public static int getHeight(BinaryTree.TreeNode root){
        if(root == null){
            return 0;
        }
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        return Math.max(left, right) + 1;
    }*/
    //O(N)
    public static boolean isBalanced(BinaryTree.TreeNode root){
        if(root == null){
            return true;
        }
        return getHeight(root) > 0;
    }
    public static int getHeight(BinaryTree.TreeNode root){
        if(root == null){
            return 0;
        }
        int left = getHeight(root.left);
        if(left == -1){
            return -1;
        }
        int right = getHeight(root.right);
        if(right == -1){
            return -1;
        }
        if(Math.abs(left - right) <= 1){
            return Math.max(left, right) + 1;
        }else {
            //当左右树高度差超过1时,返回-1
            return -1;
        }
    }
    public static void main(String[] args) {
        System.out.println(isBalanced(root));
    }
}